package com.hdu.hot100.multiDimensionalDp;

public class lc5 {
    class Solution {
        public String longestPalindrome(String s) {
            int n = s.length();
            boolean[][] dp = new boolean[n][n];
            int minLen = 1;
            int start = 0;
            for (int i = 0; i < n; i++) dp[i][i] = true;
            for (int i = n - 1; i >= 0; i--)
            {
                for (int j = i + 1; j < n; j++)
                {
                    if (s.charAt(i) != s.charAt(j)) dp[i][j] = false;
                    else dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
                    int len = j - i + 1;
                    if (len > minLen && dp[i][j])
                    {
                        minLen = len;
                        start = i;
                    }
                }
            }
            return s.substring(start, start + minLen);
        }
    }
}
